package pers.whj.util.graph;

public class GraphMatrix<T> extends AbstractGraph<T> {
    protected Object[] mVertices;
    protected int[][] mEdges;

    public GraphMatrix() {
        super();
        mVertices = new Object[mMaxVertices];
        mEdges = new int[mMaxVertices][mMaxVertices];
    }

    public GraphMatrix(int maxVertices) {
        super(maxVertices);
        mVertices = new Object[mMaxVertices];
        mEdges = new int[mMaxVertices][mMaxVertices];
    }

    @Override
    @SuppressWarnings({"unchecked"})
    protected Vertex<T> vertex(int index) {
        // assert index is valid
        return (Vertex<T>) mVertices[index];
    }

    @Override
    public boolean isCompleteGraph() {
        return mNumEdges == (long) mNumVertices / 2 * (mNumVertices - 1);
    }

    @Override
    public int getFirstNeighbor(int v) {
        checkIfVertexExists(v);
        for (int i = 0; i < mNumVertices; i++) {
            if (mEdges[v][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int getNextNeighbor(int v, int w) {
        checkIfVerticesExist(v, w);
        for (int i = w + 1; i < mNumVertices; i++) {
            if (mEdges[v][i] > 0) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int insertVertex(T vertex) {
        if (mNumVertices == mMaxVertices) {
            return -1;
        }
        mVertices[mNumVertices] = new Vertex<>(vertex);
        mNumVertices++;
        return mNumVertices - 1;
    }

    @Override
    public boolean insertEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        if (v1 == v2) {
            return false;
        }
        if (mEdges[v1][v2] > 0) {
            return false;
        }
        mEdges[v1][v2] = mEdges[v2][v1] = 1;
        mNumEdges++;
        return true;
    }

    @Override
    public boolean insertEdge(T vertex1, T vertex2) {
        return insertEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public boolean removeVertex(int v) {
        checkIfVertexExists(v);
        mVertices[v] = mVertices[mNumVertices - 1];
        for (int i = 0; i < mNumVertices; i++) {
            if (mEdges[i][v] > 0) {
                mNumEdges--;
            }
        }
        for (int i = 0; i < mNumVertices; i++) {
            mEdges[i][v] = mEdges[i][mNumVertices - 1];
        }
        mNumVertices--;
        System.arraycopy(mEdges[mNumVertices], 0, mEdges[v], 0, mNumVertices);
        return true;
    }

    @Override
    public boolean removeVertex(T vertex) {
        return removeVertex(getPosition(vertex));
    }

    @Override
    public boolean removeEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        if (mEdges[v1][v2] > 0) {
            mEdges[v1][v2] = mEdges[v2][v1] = 0;
            mNumEdges--;
            return true;
        }
        return false;
    }

    @Override
    public boolean removeEdge(T vertex1, T vertex2) {
        return removeEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public boolean hasEdge(int v1, int v2) {
        checkIfVerticesExist(v1, v2);
        return mEdges[v1][v2] > 0;
    }

    @Override
    public boolean hasEdge(T vertex1, T vertex2) {
        return hasEdge(getPosition(vertex1), getPosition(vertex2));
    }

    @Override
    public void removeAllEdges() {
        for (int i = 0; i < mNumVertices; i++) {
            for (int j = 0; j < mNumVertices; j++) {
                mEdges[i][j] = 0;
            }
        }
        mNumEdges = 0;
    }

    @Override
    public void clear() {
        removeAllEdges();
        for (int i = 0; i < mNumVertices; i++) {
            mVertices[i] = null;
        }
        mNumVertices = 0;
    }

    @Override
    public boolean resize(int maxVertices) {
        if (maxVertices < mNumVertices) {
            return false;
        }
        if (maxVertices != mMaxVertices) {
            Object[] newVertices = new Object[maxVertices];
            System.arraycopy(mVertices, 0, newVertices, 0, mNumVertices);
            mVertices = newVertices;
            mMaxVertices = maxVertices;
        }
        return true;
    }
}